nclude<iostream>
#include<algorithm>
#include<assert.h>

using std::cout;
using std::endl;

// List的节点类
template<class T>
struct ListNode
{
    ListNode(const T& val = T())
        :_pPre(nullptr),
        _pNext(nullptr),
        _val(val)
    {}
    ListNode<T>* _pPre;
    ListNode<T>* _pNext;
    T _val;
};

//List的迭代器类
template<class T, class Ref, class Ptr>
struct  ListIterator
{
    typedef ListNode<T>* PNode;
    typedef ListIterator<T, Ref, Ptr> Self;

    //给reverse_iterator 用 ，这样反向迭代器类就可以不用传后面两个参数了
    typedef  T& Ref;
    typedef  T* Ptr;

    ListIterator(PNode pNode = nullptr)
        :_pNode(pNode)
    {}
    //it1(it2)
    ListIterator(const Self& l)
    {
        _pNode = l._pNode;
    }
    //模板参数  Ref    Ptr 的作用   ，返回 const和非const对象(由传参决定)
    //(其实就是两个类了，同一个类模板，参数不同，会实例化出不同类型的对象)
    Ref operator*()
    {
        return _pNode->_val;
    }
    Ptr operator->()             //注意返回值                            
    {
        //return &(operator*());
        return &_pNode->_val;
    }
    Self& operator++()
    {
        _pNode = _pNode->_pNext;
        return*this;
    }
    Self operator++(int)
    {
        Self tmp(*this);
        _pNode = _pNode->_pNext;
        return tmp;
    }
    Self& operator--()
    {
        _pNode = _pNode->_pPre;
        return *this;
    }
    Self& operator--(int)
    {
        Self tmp = *this;
        _pNode = _pNode->_pPre;
        return tmp;
    }
    bool operator!=(const Self& l)
    {
        return !(operator==(l));
    }
    bool operator==(const Self& l)
    {
        return _pNode == l._pNode;
    }
    PNode _pNode;
};


//List的反向迭代器类
template<class ListIterator>
struct  ReverseIterator
{
    typedef typename ListIterator::Ref Ref;
    typedef typename ListIterator::Ptr Ptr;
    typedef ReverseIterator<ListIterator> Self;

    ReverseIterator(ListIterator it)
        :_it(it)
    {}
    //it1(it2)
    ReverseIterator(const Self& l)
    {
        _it = l._it;
    }

    Ref operator*()
    {
        ListIterator temp(_it);
        --temp;
        return *temp;
    }
    Ptr operator->()             //注意返回值                            
    {
        return &(operator*());
    }
    Self& operator++()
    {
        --_it;
        return *this;
    }
    Self operator++(int)
    {
        Self temp(*this);
        --_it;
        return temp;
    }
    Self& operator--()
    {
        ++_it;
        return *this;
    }
    Self& operator--(int)
    {
        Self temp(*this);
        ++_it;
        return temp;
    }
    bool operator!=(const Self& l)
    {
        return _it != l._it;
    }
    bool operator==(const Self& l)
    {
        return _it == l._it;
    }
    ListIterator _it;
};


//list类
template<class T>
class my_list
{
    typedef ListNode<T> Node;
    typedef Node* PNode;
public:
    typedef ListIterator<T, T&, T*> iterator;
    //只有后面两个加上const是因为只有这里是控制const迭代器不能修改的地方
    typedef ListIterator<T, const T&, const T&> const_iterator;

    typedef ReverseIterator<iterator> reverse_itrator;
    typedef ReverseIterator<const_iterator> const_reverse_itrator;
public:
    ///////////////////////////////////////////////////////////////
    // List的构造
    my_list()
    {
        CreateHead();
    }
    my_list(int n, const T& value = T())
    {
        CreateHead();
        for (int i = 0; i < n; i++)
        {
            push_back(value);
        }
    }
    template <class Iterator>
    my_list(Iterator first, Iterator last)
    {
        CreateHead();
        while (first != last)
        {
            push_back(*first);
            first++;
        }
    }
    //lt1(lt2)                 lt2
    my_list(const my_list<T>& l)
    {
        CreateHead();
        my_list<T> tmp(l.begin(), l.end());
        this->swap(tmp);
    }
    my_list<T>& operator=(my_list<T> l)
    {
        this->swap(l);
        return *this;
    }
    ~my_list()
    {
        clear();
        delete _pHead;
        _pHead = nullptr;
    }
    ///////////////////////////////////////////////////////////////
    // List Iterator
    iterator begin()
    {
        return iterator(_pHead->_pNext);
    }
    iterator end()
    {
        return iterator(_pHead);
    }
    const_iterator begin()const
    {
        return const_iterator(_pHead->_pNext);
    }
    const_iterator end()const
    {
        return const_iterator(_pHead);
    }

    // List Reversez_Iterator
    reverse_itrator rbegin()
    {
        return reverse_itrator(iterator);
    }
    reverse_itrator rend()
    {
        return reverse_itrator(iterator);
    }
    const_reverse_itrator crbegin()const
    {
        return const_reverse_itrator(const_iterator);
    }
    const_reverse_itrator crend()const
    {
        return const_reverse_itrator(const_iterator);
    }

    ///////////////////////////////////////////////////////////////
    // List Capacity
    size_t size()const
    {
        size_t sz = 0;
        iterator it = begin();
        while (it != end())
        {
            sz++;
            it++;
        }
        return sz;
    }
    bool empty()const
    {
        return size() == 0;
    }
    ////////////////////////////////////////////////////////////
    // List Access
    T& front()
    {
        return _pHead->_pNext->_val;
    }
    const T& front()const
    {
        return _pHead->_pNext->_val;
    }
    T& back()
    {
        return _pHead->_pPre->_val;
    }
    const T& back()const
    {
        return _pHead->_pPre->_val;
    }
    ////////////////////////////////////////////////////////////
    // List Modify
    void push_back(const T& val) { insert(end(), val); }
    void pop_back() { erase(--end()); }
    void push_front(const T& val) { insert(begin(), val); }
    void pop_front() { erase(begin()); }
    // 在pos位置前插入值为val的节点
    iterator insert(iterator pos, const T& val)
    {
        //    prev  new  cur 
        Node* newnode = new Node(val);
        Node* cur = pos._pNode;
        Node* prev = cur->_pPre;

        prev->_pNext = newnode;
        newnode->_pPre = prev;
        newnode->_pNext = cur;
        cur->_pPre = newnode;

        //返回新插入的位置
        return iterator(newnode);
    }
    // 删除pos位置的节点，返回该节点的下一个位置
    iterator erase(iterator pos)
    {
        assert(pos != end());

        Node* cur = pos._pNode;
        Node* prev = cur->_pPre;
        Node* next = cur->_pNext;

        prev->_pNext = next;
        next->_pPre = prev;
        delete cur;
        //匿名对象
        return iterator(next);
    }
    void clear()
    {
        iterator it = begin();
        while (it != end())
        {
            it = erase(it);
            it++;
        }
    }
    void swap(my_list<T>& l)
    {
        std::swap(_pHead, l._pHead);
    }
private:
    void CreateHead()
    {
        _pHead = new Node();
        _pHead->_pPre = _pHead;
        _pHead->_pNext = _pHead;
    }
    PNode _pHead;
};
